
/*
    238. 除自身以外数组的乘积
    维护两个数组，一个是从前往后乘积，另一个是从后往前乘积
    ans数组的值就是两个数组元素的乘积
    进阶：使用o(1)的额外空间来完成，用ans数组来存放pre乘积的元素，
    然后在倒着遍历的时候，用一个变量来存放当前rear的值，并实时更新ans数组元素
 */

public class ProductExceptSelf {

    public int[] productExceptSelf(int[] nums) {
        if (nums.length == 1 || nums.length == 0) return null;
        if (nums.length == 2) return new int[]{nums[1], nums[0]};
        int[] pre = new int[nums.length];
        int[] rear = new int[nums.length];
        int count = 0;
        int temp = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                temp *= nums[i];
                pre[i] = temp;
            } else count++;
        }
        int[] ans = new int[nums.length];
        if (count > 1) return ans;
        if (count == 1) {
            int a = 0;
            for (int i = 0; i < nums.length; i++) {
                if (pre[i] == 0) {
                    a = i;
                    break;
                }
            }
            temp = 1;
            for (int i = nums.length - 1; i >= 0; i--) {
                if (nums[i] != 0) {
                    temp *= nums[i];
                } else {
                    ans[a] = pre[a - 1] * temp;
                }
            }
        } else {
            temp = 1;
            for (int i = nums.length - 1; i >= 0; i--) {
                temp *= nums[i];
                rear[i] = temp;
            }
        }
        ans[0] = rear[1];
        ans[nums.length - 1] = pre[nums.length - 2];
        for (int i = 1; i < nums.length -1; i++) {
            ans[i] = pre[i - 1] * rear[i + 1];
        }
        return ans;
    }
}
